struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
    // 拷贝节点插入在原节点的后面
    while (cur) {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        copy->next = cur->next;
        cur->next = copy;

        cur = copy->next;
    }

    // 控制random
    cur = head;
    while (cur) {
        struct Node* copy = cur->next;
        if (cur->random == NULL) {
            copy->random = NULL;
        } else {
            copy->random = cur->random->next;
        }

        cur = copy->next;
    }

    // 把拷贝节点取下来尾插成为新链表，然后恢复原链表（不恢复也可以）
    struct Node* copyhead = NULL, *copytail = NULL;
    cur = head;
    while (cur)
   {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        if (copytail == NULL) {
            copyhead = copytail = copy;
        } else {
            copytail->next = copy;
            copytail = copytail->next;
        }

        // cur->next = next;
        cur = next;
    }

    return copyhead;
}